---

deRedBlack.hpp

Go to the documentation of this file.

///////////////////////////////////////////////////////////////////////////////
/// @file deRedBlack.hpp
///
/// @brief templated red-black tree
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Apr 2003
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DEREDBLACK_HPP
#define DEREDBLACK_HPP

#include "deList.hpp"

// part of this code is adapted from a Java applet demo which can be found at
// http://www.ece.uc.edu/~franco/C321/html/RedBlack/redblack.html

template <class T>
class deTRedBlack
{
    class TRBNode
    {
    public:
        explicit TRBNode()
            :Left(NULL), Right(NULL), Parent(NULL), Tree(NULL), Color(Red)
        {
        }
        TRBNode(const T & ref)
            :Data(ref), Left(NULL), Right(NULL), Parent(NULL), Tree(NULL), Color(Red)
        {
        }
        TRBNode(const TRBNode & ref)
            :Data(ref.Data), Left(NULL), Right(NULL), Parent(NULL), Tree(NULL), Color(Red)
        {
        }
        ~TRBNode()
            {}
        bool operator ==(const T & ref)
        {
            return Data == ref;
        }
        bool operator >(const T & ref)
        {
            return Data > ref;
        }
        bool operator <(const T & ref)
        {
            return Data < ref;
        }
        void CopyPtrs(const TRBNode * ref)
        {
            Left = ref->Left;
            Right = ref->Right;
            Parent = ref->Parent;
            Color = ref->Color;
        }
        template<class _Ty> inline
        void Swap(_Ty& _X, _Ty& _Y)
        {
            _Ty _Tmp(_X);
            _X = _Y;
            _Y = _Tmp; 
        }
        void SwapWith(TRBNode * Swapper, TRBNode* &Root)
        {
            if (Left)
                Left->Parent = Swapper;
            if (Right)
                Right->Parent = Swapper;
            if (Swapper->Left)
                Swapper->Left->Parent = this;
            if (Swapper->Right)
                Swapper->Right->Parent = this;
            if (Parent)
            {
                if (Parent->Left == this)
                {
                    Parent->Left = Swapper;
                }
                else if (Parent->Right == this)
                {
                    Parent->Right = Swapper;
                }
                else if (Swapper->Right == this)
                {
                    Swapper->Right = Swapper;
                }
                else if (Swapper->Left == this)
                {
                    Swapper->Left = Swapper;
                }
            }
            else
                Root = Swapper;
            if (Swapper->Parent)
            {
                if (Swapper->Parent->Left == Swapper)
                {
                    Swapper->Parent->Left = this;
                }
                else if (Swapper->Parent->Right == Swapper)
                {
                    Swapper->Parent->Right = this;
                }
                else if (Right == Swapper)
                {
                    Right = this;
                }
                else if (Left == Swapper)
                {
                    Left = this;
                }
            }
            else
                Root = this;
            Swap(Left, Swapper->Left);
            Swap(Right, Swapper->Right);
            Swap(Parent, Swapper->Parent);
            Swap(Color, Swapper->Color);
        }
        void Destroy()
        {
            if (Left)
                Left->Destroy();
            if (Right)
                Right->Destroy();
            delete this;
        }
        void AddDataToList(deTList <T*> &list)
        {
            list.AddElement(&Data);
            if (Left)
                Left->AddDataToList(list);
            if (Right)
                Right->AddDataToList(list);
        }

        TRBNode *Left, *Right;
        TRBNode *Parent;
        enum Color_t {Red, Black} Color;
        deTRedBlack * Tree;
        T Data;
    };

private:
    TRBNode * m_Root;
    long m_Length;

public:
    deTRedBlack()
    {
        m_Root = NULL;
        m_Length = 0;
    }
    ~deTRedBlack()
    {
        EmptyTree();
    }

    void EmptyTree()
    {
        if (m_Root)
            m_Root->Destroy();
        m_Root = NULL;
        m_Length = 0;
    }

    void* FindValue(const T& Val, T* &obj) const
    {
        TRBNode *Node = m_Root;
        while (Node)
        {
            if (*Node == Val)
                break;
            if (*Node > Val)
                Node = Node->Left;
            else
                Node = Node->Right;
        }
        if (!Node)
        {
            obj = NULL;
            return NULL;
        }
        else
            obj = &(Node->Data);
        return Node;
    }
    void* FindValue(const T& Val, T & obj) const
    {
        T * objptr;
        void * ptr;
        ptr = FindValue(Val, objptr);
        if (objptr)
            obj = *objptr;
        return ptr;
    }
    void* GetRoot(T* &obj) const
    {
        TRBNode *Node = m_Root;
        obj = NULL;
        if (!Node)
        {
            return NULL;
        }
        obj = &(Node->Data);
        return Node;
    }
    void * GetLeftMost(T &obj)
    {
        T * objptr;
        void * ptr;
        ptr = GetLeftMost(objptr);
        if (objptr)
            obj = *objptr;
        return ptr;
    }
    void * GetLeftMost(T* &obj)
    {
        TRBNode *Node = m_Root;
        obj = NULL;
        if (!Node)
        {
            return NULL;
        }
        while (Node->Left)
            Node = Node->Left;
        if (Node)
        {
            obj = &(Node->Data);
        }
        return Node;
    }
    void * GetLeftMostLeaf(T* &obj)
    {
        TRBNode *Node = m_Root;
        obj = NULL;
        if (!Node)
        {
            return NULL;
        }
        while (Node->Left || Node->Right)
        {
            if (Node->Left)
                Node = Node->Left;
            Node = Node->Right;
        }
        if (Node)
        {
            obj = &(Node->Data);
        }
        return Node;
    }
    void * GetNextRight(void * current, T &obj)
    {
        T * objptr;
        void * ptr;
        ptr = GetNextRight(current, objptr);
        if (objptr)
            obj = *objptr;
        return ptr;
    }
    void * GetNextRight(void * current, T* &obj)
    {
        TRBNode *Node = (TRBNode*)current;
        obj = NULL;
        if (!Node)
        {
            return NULL;
        }
        if (Node->Right)
        {
            Node = Node->Right;
            while (Node->Left)
                Node = Node->Left;
        }
        else
        if (Node->Parent)
        {
            while (Node && Node->Parent)
            {
                if (Node->Parent->Left == Node)
                {
                    Node = Node->Parent;
                    break;
                }
                else
                {
                    Node = Node->Parent;
                    if (!Node->Parent)
                        Node = NULL;
                }
            }
        }
        else
            Node = NULL;
        if (Node)
        {
            obj = &(Node->Data);
        }
        return Node;
    }
    void* AddElement(const T & data)
    {
        TRBNode *Node, *NewNode = new TRBNode(data);
        if (!NewNode)
            return NULL;

        NewNode->Tree = this;
        m_Length++;
        if (m_Root == NULL)
            m_Root = NewNode;
        else
        {
            Node = m_Root;
            while (Node != NULL)
            {
                if (*Node > data) // looks a little funky, but it's due to the operator order
                {
                    if (Node->Left)
                    {
                        Node = Node->Left;
                    }
                    else
                    {
                        Node->Left = NewNode;
                        NewNode->Parent = Node;
                        break;
                    }
                }
                else
                {
                    if (Node->Right)
                    {
                        Node = Node->Right;
                    }
                    else
                    {
                        Node->Right = NewNode;
                        NewNode->Parent = Node;
                        break;
                    }
                }
            }
        }

        RestoreRedBlack(NewNode);

        return NewNode;
    }
    static void StaticRemoveElement(void * ptr)
    {
        TRBNode * Node = (TRBNode*)ptr;
        if (Node->Tree)
            Node->Tree->RemoveElement(ptr);
    }
#pragma todo (make sure RemoveElement really works)
    deBoolean RemoveElement(void * ptr)
    {
        TRBNode * Node = (TRBNode*)ptr;
        if (Node == NULL)
            return deFALSE;
        TRBNode * DeletedNode = NULL;
        deBoolean LeftSide;

        if (Node->Left && Node->Right)
        {
            // have two children. This is the "Nasty Case"
            // but we can do a fancy trick by swapping that guarantees we have one or no children
            // we swap with one that only has one child, and "delete" that one instead
            TRBNode * Swapper = Node->Right;
            // get the smallest value that's greater than value in 'Node'
            while (Swapper->Left)
            {
                Swapper = Swapper->Left;
            }
            Swapper->SwapWith(Node, m_Root);
        }
        
        if (Node->Left || Node->Right)
        {
            // we have a single child
            if (Node->Right == NULL)
            {
                // only have a left node
                DeletedNode = Node;
                Node->Left->Parent = Node->Parent;
                if (Node->Parent)
                {
                    LeftSide = (Node->Parent->Left == Node);
                    if (LeftSide)
                    {
                        Node->Parent->Left = Node->Left;
                    }
                    else //if (Node->Parent->Right == Node)
                    {
                        Node->Parent->Right = Node->Left;
                    }
                }
                else
                    m_Root = Node->Left;
            }
            else //if (Node->Left == NULL)
            {
                // only have a right node
                DeletedNode = Node;
                Node->Right->Parent = Node->Parent;
                if (Node->Parent)
                {
                    LeftSide = (Node->Parent->Left == Node);
                    if (LeftSide)
                    {
                        Node->Parent->Left = Node->Right;
                    }
                    else //if (Node->Parent->Right == Node)
                    {
                        Node->Parent->Right = Node->Right;
                    }
                }
                else
                    m_Root = Node->Right;
            }
        }
        else
        {
            //no children, just point the parent at NULL
            DeletedNode = Node;
            if (Node->Parent)
            {
                LeftSide = (Node->Parent->Left == Node);
                if (LeftSide)
                {
                    Node->Parent->Left = NULL;
                }
                else //if (Node->Parent->Right == Node)
                {
                    Node->Parent->Right = NULL;
                }
            }
            else
                m_Root = NULL;
        }

        // deleting black affects the black-depth of the tree
        // so we need to adjust & possibly rebalance
        if (DeletedNode->Color == TRBNode::Black)
        {
            if (DeletedNode->Parent)
            {
                // if it had a child, then the child was merely moved into its place and can be re-colored to black
                if (LeftSide && DeletedNode->Parent->Left)
                {
                    DeletedNode->Parent->Left->Color = TRBNode::Black;
                    goto GoodRet;
                }
                else if (!LeftSide && DeletedNode->Parent->Right)
                {
                    DeletedNode->Parent->Right->Color = TRBNode::Black;
                    goto GoodRet;
                }
            }

            {
                // deleted node was black leaf, this is the tough one
                TRBNode RootSentinel;
                TRBNode* Sibling;
                TRBNode* Current;
                TRBNode* NodeParent;
                m_Root->Parent = &RootSentinel;
                RootSentinel.Left = m_Root;
                RootSentinel.Right = NULL;
                Current = DeletedNode;
                NodeParent = Current->Parent;
                if (NodeParent)
                    Sibling = (LeftSide) ? NodeParent->Right : NodeParent->Left;
                else
                    Sibling = NULL;
                // Loop until the current node is red, or until we get to the root node.
                while (NodeParent->Parent && Current->Color == TRBNode::Black)
                {
                    // If the sibling is red, we are unable to reduce the number of black
                    // nodes in the sibling tree, and we can't increase the number of 
                    // black nodes in our tree..  Thus we must do a rotation from the 
                    // sibling tree to our tree to give us some extra (red) nodes to 
                    // play with. This is Case 1 from the text
                    if (Sibling && Sibling->Color == TRBNode::Red)
                    {
                        NodeParent->Color = TRBNode::Red;
                        Sibling->Color = TRBNode::Black;
                        if (LeftSide)
                        {
                            leftRotate(NodeParent);
                            Sibling = NodeParent->Right;
                        }
                        else
                        {
                            rightRotate(NodeParent);
                            Sibling = NodeParent->Left;
                        }
                        continue;
                    }
                    // Sibling will be black here
                    
                    // If the sibling is black and has no red children, we have to
                    // reduce the black node count in the sibling's tree to match ours.
                    // This is Case 2a from the text.
                    if (!Sibling || 
                        ((!Sibling->Left || Sibling->Left->Color == TRBNode::Black) &&
                         (!Sibling->Right|| Sibling->Right->Color== TRBNode::Black)))
                    {
                        if (Sibling)
                            Sibling->Color = TRBNode::Red;
                        // Now we move one level up the tree to continue fixing the other branches.
                        Current = NodeParent;
                        NodeParent = Current->Parent;
                        LeftSide = (NodeParent->Left == Current);
                        Sibling = (LeftSide) ? NodeParent->Right : NodeParent->Left;
                        continue;
                    }
                    // Sibling will be black with 1 or 2 red children here

                    // << Case 2b is handled by the while loop. >>

                    // If one of the sibling's children are red, we again can't make the
                    // sibling red to balance the tree at the parent, so we have to do a
                    // rotation.  If the "near" nephew is red and the "far" nephew is
                    // black, we need to do a "prep-slide" (aka "double rotation")
                    // After doing a rotation and rearranging a few colors, the effect is
                    // that we maintain the same number of black nodes per path on the 
                    // far side of the parent, and we gain a black node on the current 
                    // side, so we are done.
                    // This is Case 4 from the text. (Case 3 is the double rotation)
                    if (LeftSide)
                    {
                        if (Sibling->Right->Color == TRBNode::Black)
                        { // Case 3 from text
                            rightSide_RightRotate(Sibling);
                            Sibling = NodeParent->Right;
                        }
                        // now Case 4 from the text
                        if (Sibling->Right->Color != TRBNode::Black ||
                            Sibling->Color != NodeParent->Color ||
                            NodeParent->Color != TRBNode::Black)
                        {
                            Sibling->Right->Color = TRBNode::Black;
                            Sibling->Color = NodeParent->Color;
                            NodeParent->Color = TRBNode::Black;
                        }
                        
                        Current = NodeParent;
                        NodeParent = Current->Parent;
                        // I would have assigned to leftSide here,
                        //   but we are exiting the function, so why bother?
                        // leftSide= (Parent->Left == Current);
                        if (NodeParent->Left == Current)
                            leftSide_LeftRotate(Current);
                        else
                            rightSide_LeftRotate(Current);
                        goto GoodRet;
                    }
                    else
                    {
                        if (Sibling->Left->Color == TRBNode::Black)
                        { // Case 3 from text
                            leftSide_LeftRotate(Sibling);
                            Sibling = NodeParent->Left;
                        }
                        // Case 4 from the text
                        if (Sibling->Left->Color != TRBNode::Black ||
                            Sibling->Color != NodeParent->Color ||
                            NodeParent->Color != TRBNode::Black)
                        {
                            Sibling->Left->Color = TRBNode::Black;
                            Sibling->Color = NodeParent->Color;
                            NodeParent->Color = TRBNode::Black;
                        }
                        
                        Current = NodeParent;
                        NodeParent = Current->Parent;
                        // I would have assigned to leftSide here,
                        // but we are exiting the function, so why bother?
                        // leftSide = (Parent->Left == Current);
                        if (NodeParent->Left == Current)
                            leftSide_LeftRotate(Current);
                        else
                            rightSide_LeftRotate(Current);
                        goto GoodRet;
                    }
                    // Now, make the current node black (to fulfill Case 2b)
                    // Case 4 will have exited directly out of the function.
                    // If we stopped because we reached the top of the tree,
                    //   the head is black anyway so don't worry about it.
                    Current->Color = TRBNode::Black;
                }
                m_Root = RootSentinel.Left;
                if (m_Root)
                    m_Root->Parent = NULL;
            }
        }
GoodRet:
        if (m_Root)
            DE_ASSERT(m_Root->Color == TRBNode::Black);
        delete Node;
        m_Length--;
        return deTRUE;
    }
    T* GetData(void* ptr)
    {
        TRBNode * Node = (TRBNode*)ptr;
        if (Node == NULL)
            return NULL;
        return &(Node->Data);
    }
    void GetDataPList(deTList <T*> &list)
    {
        if (m_Root)
            m_Root->AddDataToList(list);
    }
    long Length() const
    {
        return m_Length;
    }
private:
    void RestoreRedBlack(TRBNode * Node)
    {
        if (!Node)
            return;
        TRBNode* Uncle;
        /* Now restore the red-black property */
        Node->Color = TRBNode::Red;
        while ( (Node != m_Root) && (Node->Parent->Color == TRBNode::Red) )
        {
            if ( Node->Parent == Node->Parent->Parent->Left )
            {
                /* If x's parent is a left, y is x's right 'uncle' */
                Uncle = Node->Parent->Parent->Right;
                if (Uncle && Uncle->Color == TRBNode::Red )
                {
                    /* case 1 - change the colours */
                    Node->Parent->Color = TRBNode::Black;
                    Uncle->Color = TRBNode::Black;
                    Node->Parent->Parent->Color = TRBNode::Red;
                    /* Move x up the tree */
                    Node = Node->Parent->Parent;
                }
                else
                {
                    /* y is a black node */
                    if ( Node == Node->Parent->Right )
                    {
                        /* and x is to the right */ 
                        /* case 2 - move x up and rotate */
                        Node = Node->Parent;
                        RotateLeft( Node );
                    }
                    /* case 3 */
                    Node->Parent->Color = TRBNode::Black;
                    Node->Parent->Parent->Color = TRBNode::Red;
                    RotateRight( Node->Parent->Parent );
                }
            }
            else
            {
                /* If x's parent is a right, y is x's left 'uncle' */
                Uncle = Node->Parent->Parent->Left;
                if (Uncle && Uncle->Color == TRBNode::Red )
                {
                    /* case 1 - change the colours */
                    Node->Parent->Color = TRBNode::Black;
                    Uncle->Color = TRBNode::Black;
                    Node->Parent->Parent->Color = TRBNode::Red;
                    /* Move x up the tree */
                    Node = Node->Parent->Parent;
                }
                else
                {
                    /* y is a black node */
                    if ( Node == Node->Parent->Left )
                    {
                        /* and x is to the right */ 
                        /* case 2 - move x up and rotate */
                        Node = Node->Parent;
                        RotateRight( Node );
                    }
                    /* case 3 */
                    Node->Parent->Color = TRBNode::Black;
                    Node->Parent->Parent->Color = TRBNode::Red;
                    RotateLeft( Node->Parent->Parent );
                }
            }  
        }
        /* Colour the root black */
        m_Root->Color = TRBNode::Black;
    }
    void RotateLeft(TRBNode * Node)
    {
        TRBNode * y;
        y = Node->Right;
        /* Turn y's left sub-tree into x's right sub-tree */
        Node->Right = y->Left;
        if ( y->Left != NULL )
            y->Left->Parent = Node;
        /* y's new parent was x's parent */
        y->Parent = Node->Parent;
        /* Set the parent to point to y instead of x */
        /* First see whether we're at the root */
        if ( Node->Parent == NULL )
            m_Root = y;
        else
        {
            if ( Node == (Node->Parent)->Left )
                /* x was on the left of its parent */
                Node->Parent->Left = y;
            else
                /* x must have been on the right */
                Node->Parent->Right = y;
        }
        /* Finally, put x on y's left */
        y->Left = Node;
        Node->Parent = y;   
    }
    void RotateRight(TRBNode * Node)
    {
        TRBNode * y;
        y = Node->Left;
        /* Turn y's right sub-tree into x's left sub-tree */
        Node->Left = y->Right;
        if ( y->Right != NULL )
            y->Right->Parent = Node;
        /* y's new parent was x's parent */
        y->Parent = Node->Parent;
        /* Set the parent to point to y instead of x */
        /* First see whether we're at the root */
        if ( Node->Parent == NULL )
            m_Root = y;
        else
        {
            if ( Node == (Node->Parent)->Right )
                /* x was on the right of its parent */
                Node->Parent->Right = y;
            else
                /* x must have been on the left */
                Node->Parent->Left = y;
        }
        /* Finally, put x on y's right */
        y->Right = Node;
        Node->Parent = y;   
    }

    void rightRotate(TRBNode* node)
    {
        if (node->Parent->Left == node)
            leftSide_RightRotate(node);
        else
            rightSide_RightRotate(node);
    }
    
    void leftRotate(TRBNode* node)
    {
        if (node->Parent->Left == node)
            leftSide_LeftRotate(node);
        else
            rightSide_LeftRotate(node);
    }
    
    void leftSide_LeftRotate(TRBNode* node)
    {
        TRBNode* temp = node->Parent; // temp is used for parent
        TRBNode* child = node->Right;
        
        temp->Left = child;
        child->Parent = temp;
        
        temp = child->Left; // temp is now used for grandchild
        node->Right = temp;
        temp->Parent = node;
        
        child->Left = node;
        node->Parent = child;
    }
    
    void leftSide_RightRotate(TRBNode* node)
    {
        TRBNode* temp = node->Parent; // temp is used for parent
        TRBNode* child = node->Left;
        
        temp->Left = child;
        child->Parent = temp;
        
        temp = child->Right; // temp is now used for grandchild
        node->Left = temp;
        temp->Parent = node;
        
        child->Right = node;
        node->Parent = child;
    }
    
    void rightSide_RightRotate(TRBNode* node)
    {
        TRBNode* temp = node->Parent; // temp is used for parent
        TRBNode* child = node->Left;
        
        temp->Right = child;
        child->Parent = temp;
        
        temp = child->Right; // temp is now used for grandchild
        node->Left = temp;
        temp->Parent = node;
        
        child->Right = node;
        node->Parent = child;
    }
    
    void rightSide_LeftRotate(TRBNode* node)
    {
        TRBNode* temp = node->Parent; // temp is used for parent
        TRBNode* child = node->Right;
        
        temp->Right = child;
        child->Parent = temp;
        
        temp = child->Left; // temp is now used for grandchild
        node->Right = temp;
        temp->Parent = node;
        
        child->Left = node;
        node->Parent = child;
    }

};

//#pragma warning (default : 4710)

#endif // DEREDBLACK_HPP

---